package leetcode每日一题.leetcode20212.滑动窗口;

/**
 * 1. 问题描述
 *      几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
 *      每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
 *      你的点数就是你拿到手中的所有卡牌的点数之和。
 *      给你一个整数数组cardPoints和整数 k，请你返回可以获得的最大点数。
 *
 * 2. 算法分析
 *     转化思路：题目要求是从头或者尾取牌，直到取出k张牌，牌的总和最大
 *     转化：取出n-k张连续的牌是得牌的总和最小，此时问题从离散变化为连续，由此可以使用滑动窗口算法实现
 *     整体思路和Q001一样，是一类题目
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q002_可获得的最大点数 {

    /**
     * 转化题目，使用滑动窗口
     * @param cardPoints
     * @param k
     * @return
     */
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length; // 牌的总数
        int count = n - k;
        int sum = 0; // 记录总点数和
        for(int i = 0; i < n; i++) {
            sum += cardPoints[i];
        }
        if(k == n) {
            return sum;
        }
        int points = Integer.MAX_VALUE; // 记录全局的最小点数(连续牌组的)
        int left = 0;
        int right = 0;
        int temp = 0; // 记录当前窗口的牌的点数和
        // 注意：下面的right++的位置决定了我们使用的窗口为左闭右开的区间，即[left,right)
        while(right < n) {
            temp += cardPoints[right];
            right++;
            if(right - left == count) { // 判断当前窗口是否扫描完成，即取出了连续的count张牌
                points = Math.min(points,temp);
                if(left == n) {
                    break;
                }
                temp -= cardPoints[left];
                left++;
            }
        }
        return sum - points;
    }
}
